﻿//day24-01 牛客：判断是不是平衡⼆叉树，题号：23250
//解法：递归：宏观角度看待递归，并且只考虑在某个节点干什么事
//bool IsBalanced_Solution(TreeNode* pRoot)
//{
//    return (dfs(pRoot) == -1 ? false : true);
//}
//int dfs(TreeNode* pRoot)// 返回值不是-1的话，其余的返回值表示的是树高
//{
//    if (pRoot == nullptr) return 0;
//    int left = dfs(pRoot->left);
//    if (left == -1) return -1;//剪枝
//    int right = dfs(pRoot->right);
//    if (right == -1) return -1;//剪枝
//    return abs(left - right) <= 1 ? max(left, right) + 1 : -1;
//}


//day24-02 牛客：最⼤⼦矩阵，题号：23655
//解法：二维前缀和
//int arr[110][110];
//int dp[110][110];
//int n;
//int main()
//{
//    cin >> n;
//    for (int i = 1; i <= n; i++)
//        for (int j = 1; j <= n; j++)
//            cin >> arr[i][j];
//
//    for (int i = 1; i <= n; i++)
//        for (int j = 1; j <= n; j++)
//            dp[i][j] = dp[i - 1][j] + dp[i][j - 1] - dp[i - 1][j - 1] + arr[i][j];
//    int ret = -0x3f3f3f3f;
//    for (int x1 = 1; x1 <= n; x1++)
//    {
//        for (int y1 = 1; y1 <= n; y1++)
//        {
//            for (int x2 = x1; x2 <= n; x2++)
//            {
//                for (int y2 = y1; y2 <= n; y2++)
//                {
//                    ret = max(ret, dp[x2][y2] - dp[x2][y1 - 1] - dp[x1 - 1][y2] + dp[x1 - 1][y1 - 1]);
//                }
//            }
//        }
//    }
//    cout << ret << endl;;
//    return 0;
//}


//day24-02 牛客：小葱的01串，题号：2310079
//解法：滑动窗口
//int n;
//string s;
//int main()
//{
//    cin >> n >> s;
//    int zero = 0, one = 0;
//    for (auto ch : s)
//    {
//        if (ch == '0') zero++;
//        else one++;
//    }
//    if (zero % 2 || one % 2) cout << 0;
//    else
//    {
//        int tmp1 = zero / 2;
//        int tmp2 = one / 2;
//        int count1 = 0, count2 = 0;
//        int ret = 0;
//        for (int left = 0, right = 0; right < n; right++)
//        {
//            if (s[right] == '0') count1++;
//            else count2++;
//            while (count1 > tmp1 || count2 > tmp2)
//            {
//                if (s[left] == '0') count1--;
//                else count2--;
//                left++;
//            }
//            if (count1 == tmp1 && count2 == tmp2) ret++;
//        }
//        count1 = 0, count2 = 0;
//        for (int left = 1, right = 1; right < n - 1; right++)
//        {
//            if (s[right] == '0') count1++;
//            else count2++;
//            while (count1 > tmp1 || count2 > tmp2)
//            {
//                if (s[left] == '0') count1--;
//                else count2--;
//                left++;
//            }
//            if (count1 == tmp1 && count2 == tmp2) ret++;
//        }
//        cout << ret;
//    }
//    return 0;
//}